package com.hy.day;

import java.util.Arrays;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:1738. 找出第 K 大的异或坐标值
 * User:Mr.Du
 * Date:2024/5/26
 * Time:12:18
 */
public class KthLargestValue {

    /**
     * 计算矩阵中第k大的值
     *
     * @param matrix 一个二维整数矩阵
     * @param k 指定要找到的第k大值
     * @return 返回矩阵中第k大的值
     */
    public int kthLargestValue(int[][] matrix, int k) {
        // 获取矩阵的行数和列数
        int m = matrix.length, n = matrix[0].length;
        // 创建一个二维数组用于存储每个位置的前缀异或结果
        int[][] pre = new int[m+1][n+1];
        // 创建一个一维数组用于存储所有位置的异或结果
        int[] res = new int[m * n];
        int idx = 0;
        // 计算每个位置的前缀异或值，并将所有位置的异或结果存入res数组
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                pre[i][j] = pre[i-1][j] ^ pre[i-1][j-1] ^ pre[i][j-1] ^ matrix[i-1][j-1];
                res[idx++] = pre[i][j];
            }
        }
        // 对res数组进行排序
        Arrays.sort(res);
        // 返回res数组中第k大的值（由于数组是从0开始的，所以实际是res[m * n - k]）
        return res[m * n - k];
    }
}
